1. Field of the Invention
The present invention relates generally to networked digital computers, and, more particularly, distributed caching of digital data throughout the network of computers.
2. Description of the Prior Art
Present file systems for digital computers employ a wide range of caching mechanisms to accelerate performance. There are data caches, name caches, attribute caches, client caches, and many other kinds of caches. Clients receiving data from such caches via a network generally demand that the data be consistent with the original source data structure, although there are some applications where the clients don't require a very high degree of consistency. However, file systems clients usually want all the consistency that the file system can deliver.
There are two basic methods for maintaining consistency of data cached at remote sites, client-driven consistency, and server-driven consistency. In client-driven consistency, clients fetch the file-last-write-time attribute from the file server, a process that is frequently referred to colloquially as "pinging the server," and then compare that time with the file-last-write-time attribute associated with the cached data. Since the file-last-write-time attribute for the cached data was loaded into the cache at the same time as the cached data, if the times both at the file server and the client are the same, the file has not been modified since the cached data was fetched from the server, and the cached file data remains valid. If the times differ, the file has been modified so all cached file data is now invalid, must be discarded, and new file data fetched from the server.
Client-driven consistency provides weak consistency since the file may change just after the server has responded to a ping, and the client won't detect the file's change until the next ping.
While increasing the ping rate tightens the consistency, the improved consistency comes at the expense of reduced scalability. Moreover, with client-driven cache consistency the server's response to each client ping always reports the file's state at the moment the server processes the ping-request, and the data in the file may change immediately thereafter while the client is using the data. Consequently, regardless of how frequently the client pings the server, there always remains a window of uncertainty regarding the validity of remotely cached data.
For server-driven consistency, the file server monitors all clients accessing a file and tracks the types of operations (e.g. read or write) being performed by each client. Clients are allowed to cache data locally if no concurrent write sharing ("CWS") condition exists. (A CWS condition exists if multiple clients are active on a file and at least one of them is writing to the file.) If a server detects a CWS condition, it sends a message to all caching sites instructing them that:
a) the cached file image is to be flushed back to the server if it contains modified data; and/or PA1 b) the file image which they are caching is to be invalidated. PA1 1. if data of a previously cached but now inactive file remains valid; and PA1 2. if the data in the file remains valid, to supply the data to a client without re-retrieving the file from the file's remote server.
Thus, if a CWS condition arises, all client caches are "turned off," and all client requests flow through to the server, where they are serviced from the file server's cache, which is common for all clients.
Server-driven consistency has an advantage in that it provides `absolute` consistency so long as a server or network failure doesn't prevent a consistency message (e.g. RecallAndInvalidate or Invalidate message) from being delivered to the client. Server-driven consistency suffers from the disadvantage that it scales poorly to large networks that are distributed over a large geographic distance since the sever must keep track of every file being accessed.
One widely used Unix file system called Network File System ("NFS") employs the client-driven cache consistency method. NFS clients typically ping the file server every 3 seconds for every file that is in use. This pinging generates a substantial amount of network traffic and limits the scalability of NFS. In addition, NFS offers weak consistency semantics. Clients usually employ a file locking mechanism, such as Revision Control System ("RCS") or Source Code Control System ("SCCS"), that is external to NFS to avoid a concurrent write sharing condition. Furthermore, NFS client caches reside only in main memory and are managed on a least recently used ("LRU") basis. Consequently, the cache size is limited to the amount of memory available. NFS requires continual communication with the server for every file in use. The constant communication stream that binds clients to servers is not well suited for a network operating over a geographically large distance.
Another file system called Andrew File System ("AFS") caches files on the local disk of client systems. Whenever a file is opened, the client pings the server to determine if the cached file is current. If so, the cached file is used. If not, a new copy of the file is loaded (or at least the first "chunk" is loaded) before the open call returns to the calling program. AFS guarantees that the cached file is most likely current at the moment the open call returns. Once the open call returns, the client process uses the file with no additional communication with the server. AFS is highly scalable since clients only ping the server once each time a file is opened, but the consistency guarantee provided by AFS is very weak. AFS is very scalable in two ways. First, since files are re-validated each time they're opened, clients may cache an unlimited number of files. Second, since client machines only require a single ping to re-validate a file, and then no further server communication is required, the client machines may be distributed over a geographically very large area.
Later versions of a remote file system protocol named Server Message Block ("SMB") implement a server-driven "opportunistic locks" ("oplocks") mechanism. An SMB server grants clients permission to cache file data, monitors all file requests, and revokes caching privileges as required to ensure that all clients have exactly the same view of file data at any given instant. This method provides "absolute" consistency, which means that a read-request for a file always returns the most recently written data, except when a network failure prevents the server's oplock break message from being delivered to a client.
In principle, SMB allows clients to buffer (cache) file data only as long as the file is held open on the client machine. SMB's "batch oplock" allows a file to persist in the cache for a short interval after the last close. There may be multiple processes holding a file open on the client system, but even using batch oplocks shortly after the last process holding the file open closes the file, SMB invalidates all cached data associated with the file. Thus, clients are limited to caching only those files that are in active use (i.e. are being held open by one or more processes).
SMB does not support long term caching. This implies that whenever a file is initially opened at a client it must be fetched across the network which may be quite distant from the client. A file system capable of operating over geographically large distances must allow long-term (e.g. months or even years) file caching, and only transmit a copy of a file across the net if the cached copy becomes invalid.
The preceding comparison of client-driven and server-driven methods for maintaining cache consistency reveal that, presuming a reliable network interconnects a server and a client, server-driven methods maintain absolute consistency by monitoring all file traffic, detecting occurrence of CWS, and recalling/invalidating cached file images as required. Server-driven methods, such as SMB, do not require or use file time stamps. Conversely, client-driven methods are essentially strategies for accessing disconnected file images. NFS client caches continuously ping the server, (i.e. retrieve the file-last-write-time attribute) to re-validate cached file images. AFS clients ping the server only once when the file is opened, reload the cached file image if necessary, and then use the cached file image until the file is closed without additional consistency checking.